1. Field of the Invention
The present invention relates to a packet scheduling scheme based on the weighted fair queueing in which packet outputs are scheduled without using a sorting processing.
2. Description of the Background Art
The conventionally available Internet based on IP (Internet Protocol) has been a best-effort network which is aimed at sure delivery of packets to their destinations without failure, without guaranteeing QOS (Quality Of Service) such as network delay. However, in the Internet of the recent years, there is a transition to an architecture that accounts for the guarantee of QOS. In such a case, the QOS is to be guaranteed for each "flow" which is defined by a source address, a destination address, a protocol number, a TCP/UDP port number, etc. that are specified in the IP packet header.
On the packet transfer level, packet queues are provided in correspondence to flows, and the packet queue scheduling is carried out. A known packet queue scheduling scheme includes a weighted fair queueing that gives different weights to different flows according to their utilization bandwidths, and services the packet queues fairly by accounting for the packet lengths at a rate according to the weights. Specific algorithms for this weighted fair queueing include an algorithm called SCFQ (Self-Clocked Fair Queueing) as disclosed in: S. J. Golestani, "A Self-Clocked Fair Queueing Scheme for Broadband Applications", Proc. of IEEE INFOCOM '94, pp. 636-646, 1994, and a similar algorithm called Virtual Clock as disclosed in: L. Zhang, "Virtual Clock: A New Traffic Control Algorithm for Packet Switching Networks", Proc. of ACM SIGCOMM '90, pp. 18-29, 1990.
In general, in the weighted fair queueing, a timestamp calculated according to a weight or an arriving packet length is attached to a packet or a packet queue, and a packet with a smaller timestamp or a packet in a packet queue with a smaller timestamp is sequentially selected and outputted in principle. Here, in order to select a packet or a packet queue with the smallest timestamp from all output candidates, there is a need for the sorting processing or the semi-ordered tree management, and the amount of calculations required for them is in an order of log.sub.2 N, where N is a number of flows.
In view of this fact, there has been a proposition for a type of packet scheduling algorithm called DRR (Deficit Round Robin) which does not call for the sorting, as disclosed in: M. Shreedhar and G. Varghese, "Efficient Fair Queueing using Deficit Round Robin", Proc. of ACM SIGCOMM '95, pp. 231-242, 1995.
In the following, the principle of the DRR will be described briefly.
As shown in FIG. 1, the DRR uses packet queues 120 provided in correspondence to flows in conjunction with an active list which holds flow IDs of (active) packet queues in which packets are currently queued and a counter which indicates a number of bytes that are currently transmittable by each flow. Here, weights of the flows a, b, c and d will be denoted as w.sub.a, w.sub.b, w.sub.c and w.sub.d (bytes). Note that these weights are to be set greater than or equal to the maximum packet length.
In FIG. 1, a character string appearing in each packet indicates a packet identification information. For example, a packet with an indication "b3(200)" is the third arrived packet of the flow b, whose packet length is 200 bytes. In this example, it is assumed that there are four flows a, b, c and d.
A Next field of the active list holds a flow ID of a next active packet queue. In addition, the active list also has pointers for pointing flow IDs of table entries that are head, tail and currently selected ones among the active flows, which are respectively denoted as Head, Tail and Now. In FIG. 1, entries for the flows a, b, d are linked in this order, so that Head points to the flow a, Tail points to the flow d and Now points to the flow a. A value of Now is initially set at Head, and reset to Head when it reaches to Tail. A time period by which Now goes around from Head to Tail once will be called a round.
Now, assuming that w.sub.a =w.sub.b =w.sub.c =w.sub.d =500 (bytes), the weight 500 is entered into the counter as an initial value. A packet output unit 130 reads out a flow ID f (f=a in this example) from the entry pointed by Now in the active list, and continues to output packets from the corresponding packet queue 120 as long as a difference between a value of the corresponding counter and a packet length of a top packet in the corresponding packet queue 120 is greater than or equal to 0 and the corresponding packet queue 120 is active, while decrementing a value of the corresponding counter as much as a packet length of each outputted packet. Then, a value of the corresponding counter is incremented by Wf if the corresponding packet queue 120 is still active, whereas a value of the corresponding counter is set equal to W.sub.f otherwise, and then, Now is updated. Now is reset to Head if Now has already been at Tail, whereas Now is set at the next entry otherwise. Then, the similar processing is repeated for the entry newly pointed by Now.
When the packet queue 120 becomes active due to an arrival of a packet, the active list is immediately updated. For example, in FIG. 1, when the packet queue 120 for the flow c becomes active, the Next field of the table entry for the flow b is changed from d to c, and the Next field of the table entry for the flow c is set to be d.
In a situation depicted in FIG. 1, assuming that no packet newly arrives, the packet output sequence within one round will be: a1(100), b1(300), b2(100), d1(300), d2(100); and values of the counters for the flows a, d, c and d at the end of one round will be 900, 600, 500 and 500, respectively. Namely, in the DRR, for each flow from which a next packet could not have been outputted because a packet length of that next packet was greater than the counter value in the previous round, a number of bytes that were allowed to be outputted but not actually outputted in the previous round will be added to the counter value for the next round so that as many number of bytes more than the weight can be outputted in the next round.
According to this DRR, a time required for the packet output unit 130 to select the next output packet becomes constant regardless of a number of flows. In addition, it is possible to guarantee the maximum value of the delay when the flow input traffic obeys the reported traffic parameter, as well as the fairness in a time scale longer than one round.
However, in the DRR, once the flow is selected, it will continue to select packets from the same flow until it becomes no longer possible to decrement the counter or the packet queue becomes empty, so that the burstiness for each flow becomes large in a time period shorter than one round, and the fairness characteristic will be degraded. This tendency becomes more prominent when the maximum packet length becomes longer, that is, when the minimum value of the weight becomes larger.
Thus the DRR, which is one example of the conventional weighted fair queueing algorithms, is associated with the problem that the fairness characteristic is degraded because the burstiness for each flow becomes large in a time period shorter than one round.